﻿namespace Leetcode.N0212;

public class Solution
{
    public IList<string> FindWords(char[][] board, string[] words)
    {
        var reslut = new System.Collections.Generic.List<string>();
        var heads = this.GetHeads(board);
        var trie = new Trie();
        foreach (var item in words)
        {
            trie.Insert(item);

        }

        foreach (var node in trie.children)
        {
            if (node == null)
            {
                continue;
            }

            if (!heads.ContainsKey(node.key))
            {
                continue;
            }
            bool[][] visited = new bool[board.Length][];
            for (int row = 0; row < board.Length; row++)
            {
                visited[row] = new bool[board[0].Length];
            }
            var result = new List<string>();

            foreach (var item in heads[node.key])
            {
                this.Search(node, board, item.row, item.col, visited, reslut);
            }
        }
        return reslut;
    }
    private void Search(Trie trie, char[][] board, int row, int col, bool[][] visited, IList<string> result)
    {

        if (row < 0 || row >= board.Length || col < 0 || col >= board[0].Length)
        {
            return;
        }

        if (trie.key != board[row][col])
        {
            return;
        }

        if (visited[row][col])
        {
            return;
        }

        if (trie.value != null && trie.output == false)
        {
            trie.output = true;
            result.Add(trie.value);

        }

        visited[row][col] = true;

        var next = new (int row, int col)[] { (row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1) };
        foreach (var n in next)
        {
            if (trie.children == null)
            {
                continue;
            }
            foreach (var item in trie.children)
            {
                if (item == null)
                {
                    continue;
                }
                this.Search(item, board, n.row, n.col, visited, result);
            }

        }
        visited[row][col] = false;
    }

    private IDictionary<char, IList<(int row, int col)>> GetHeads(char[][] board)
    {
        var heads = new Dictionary<char, IList<(int row, int col)>>();
        for (int row = 0; row < board.Length; row++)
        {
            for (int col = 0; col < board[row].Length; col++)
            {
                if (!heads.ContainsKey(board[row][col]))
                {
                    heads.Add(board[row][col], new List<(int row, int col)>());
                }
                heads[board[row][col]].Add((row, col));
            }
        }
        return heads;
    }
}


public class Trie
{

    public string value;
    public Trie[] children;

    public char key;

    public bool output;
    public Trie()
    {
    }

    public Trie(char key)
    {
        this.key = key;
    }

    public char Key => key;

    public void Insert(string word)
    {
        this.Insert(word, 0);
    }

    private void Insert(string word, int index)
    {
        if (this.children == null)
        {
            this.children = new Trie[26];
        }

        var node = this.children[word[index] - 'a'];
        if (node == null)
        {
            node = new Trie(word[index]);
            this.children[word[index] - 'a'] = node;
        }

        if (index == word.Length - 1)
        {
            node.value = word;
        }
        else
        {
            node.Insert(word, index + 1);
        }
    }
    public bool Search(string word)
    {
        return this.Search(word, 0);
    }

    private bool Search(string word, int index)
    {
        if (this.children == null)
        {
            return false;
        }
        var node = this.children[word[index] - 'a'];
        if (node == null)
        {
            return false;
        }

        if (index == word.Length - 1)
        {
            return node.value != null;
        }
        else
        {
            return node.Search(word, index + 1);
        }
    }

    public bool StartsWith(string prefix)
    {
        return this.StartsWith(prefix, 0);
    }

    private bool StartsWith(string prefix, int index)
    {
        if (this.children == null)
        {
            return false;
        }

        var node = this.children[prefix[index] - 'a'];
        if (node == null)
        {
            return false;
        }

        if (index == prefix.Length - 1)
        {
            return true;
        }

        return node.StartsWith(prefix, index + 1);
    }
}
